class Solution(object):
    def getHappyString(self, n, k):
        self.out = []
        out = []

        def dfs(i):
            if i == n:
                self.out.append(''.join(out))
            else:
                for t in ['a', 'b', 'c']:
                    if i == 0:
                        out.append(t)
                        dfs(i + 1)
                        out.pop()
                    else:
                        if t != out[-1]:
                            out.append(t)
                            dfs(i + 1)
                            out.pop()

        dfs(0)
        if k > len(self.out):
            return ''
        return self.out[k - 1]
